package my.algo.tree;

import java.util.LinkedList;

/**
 * 平衡查找树：任一节点的左子树和右子树深度差不超过1。
 * 平衡二叉树根据发明者的名字又称AVL树（Adelson-Velskii和Laandis）是最先发明的自平衡二叉查找树。
 * 在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。
 * 红黑树是自平衡二叉查找树，非平衡二叉查找树，用标准的二叉树和一些额外信息来表示一颗2-3树。
 * @author fengbo
 * @date 2018/8/6
 */
public class RedBlackBST<T extends Comparable<T>> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    private RedBlackBST<T> put(T value) {
        root = put(root, value);
        root.color = BLACK;
		return this;
    }

    private Node put(Node h, T value) {
        if (h == null) {
            return new Node(value, 1, RED);
        }
        int cmp = value.compareTo(h.value);
        if (cmp < 0) {
            h.left = put(h.left, value);
        } else if (cmp > 0) {
            h.right = put(h.right, value);
        }

        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }
        h.n = size(h.left) + size(h.right) + 1;
        return h;
    }

    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    public int size() {
        return size(root);
    }

    public int size(Node x) {
        if (x == null) {
            return 0;
        }
        return x.n;
    }

    private boolean isRed(Node x) {
        return x != null && x.color == RED;
    }

    private class Node {
        T value;
        Node left, right;
        int n;
        boolean color;

        Node(T value, int n, boolean color) {
            this.value = value;
            this.n = n;
            this.color = color;
        }
    }

    public void recursiveTraversal() {
		recursiveTraversal(root);
	}	

	private void recursiveTraversal(Node root) {
		if (root != null) {
			System.out.print(root.value + " ");
			recursiveTraversal(root.left);
			recursiveTraversal(root.right);
		}
	}
	
    public void levelTraversal() {
		LinkedList<Node> queue = new LinkedList<>();
		queue.addLast(root);
		Node last = root;
		Node temp = null;
		while (!queue.isEmpty()) {
			Node node = queue.removeFirst();
			System.out.print(node.value + " ");
			if (node.left != null) {
				queue.addLast(node.left);
				temp = node.left;
			}
			if (node.right != null) {
				queue.addLast(node.right);
				temp = node.right;
			}
			if (node.value.equals(last.value)) {
				System.out.println();
				last = temp;
			}
		}
	}	

    public static void main(String[] args) {
        RedBlackBST<Integer> test = new RedBlackBST<>();
        test.put(10).put(20).put(40).put(50).put(60);
        test.put(70).put(80).put(90).put(100).put(110);
        test.put(120).put(130).put(25).put(26);
		test.levelTraversal();
    }
}
